#include<bits/stdc++.h>
#define N 5000005

int T,P,n,m;

inline int fmo(int x){
	return x+((x>>31)&P);
}
inline int fp(int x,int k=P-2){
	int res=1;
	for(;k;k>>=1,x=1ll*x*x%P)
		if(k&1)
			res=1ll*res*x%P;
	return res;
}

int fac[N],inv[N],ifac[N];
inline void init(int x){
	fac[0]=1;
	for(int i=1;i<=x;i++)
		fac[i]=1ll*fac[i-1]*i%P;
	inv[1]=1;
	for(int i=2;i<=x;i++)
		inv[i]=fmo(-1ll*P/i*inv[P%i]%P);
	ifac[0]=1;
	for(int i=1;i<=x;i++)
		ifac[i]=1ll*ifac[i-1]*inv[i]%P;
}
inline int C(int x,int y){
	if(x<0||y<0||x<y)
		return 0;
	return 1ll*fac[x]*ifac[y]%P*ifac[x-y]%P;
}

int main(){
	freopen("pr.in","r",stdin);
	freopen("pr.out","w",stdout);
	scanf("%d",&P);
	init(5e6);
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		int res=0;
		for(int i=0;i<=n+n&&(m+1)*i<=m*n;i++)
			res=fmo(res+1ll*(i&1?fmo(-1):1)*C(n+n,i)%P*C(n+n-1+m*n-(m+1)*i,n+n-1)%P-P);
		res=1ll*fmo(1-1ll*res*fp(fp(m+1,n+n))%P)*(P+1)/2%P;
		printf("%d\n",res);
	}
}
